1. Field of the Invention
The present invention relates to techniques for compressing images. More specifically, the present invention relates to a method and an apparatus that facilitates fast, lossless image compression using color palettes.
2. Related Art
Modern computing applications typically process image data. For example, remote computing applications allow screen information that is generated generated on one computer—the host computer—to be transmitted and displayed on another computer—the display computer. These display computers can include a multipurpose computer, an X-terminal, a thin client, or a personal digital assistant (PDA). The latter three are limited-purpose computers that may have no hard drive, have limited computing capabilities, and are designed for only remote computing applications.
The communication between the host and display computers can occur over any sort of network connection (e.g. Ethernet, wireless). The number of bits that can be sent per second on a network connection is the “network bandwidth” of that network connection. This network bandwidth is limited mainly by two factors: (1) the physical composition of the network, and (2) the communication protocol used on the network (i.e. TCP/IP). If the network is a shared network, the network bandwidth available to an individual computer is further limited by the network bandwidth used by the other computers on the network.
Remote computer applications typically have a minimum network bandwidth requirement. If the network bandwidth available on the network connection falls below this minimum, the application either ceases functioning entirely or the user experience becomes unacceptable. Reducing the minimum network bandwidth required by a remote computer application thus has two beneficial effects: (1) the application is usable in networks with less network bandwidth available; and (2) more devices can share the same network bandwidth.
During typical remote computing usage, including web browsing, the host/display network bandwidth will, in many cases, be dominated by the transmission of images with a large number of colors. Examples of such images include, digital photographic images of the natural world, computer-generated images of the natural world, and computer-generated images, which include anti-aliased text or graphics. There are several image compression schemes available such as the Graphics Interchange Format (GIF) from CompuServe Interactive Services, Inc. These alternate compression schemes typically require significant computing power and/or provide poor compression ratios. Additionally, these compression schemes do not achieve optimal compression for images, which are dominated by a small number of frequent colors, but also have a few rare colors, for example, anti-aliased text.
Some remote display applications use RGB image codecs to compress these images for lower-bandwidth transmission. These codecs typically take advantage of spatial coherence in the image to achieve compression. While such RGB image codecs are generally very good at achieving compression, and hence at reducing the bandwidth requirement, they often require a significant amount of computational power. In situations where this computational power may not be available, other compression schemes that might be less efficient at compression but require less computational power are desirable. In addition, RGB image codecs generally achieve good compression at the expense of accuracy; they are often “lossy” (i.e. some image information gets lost during compression). This may be undesirable in some applications.
Image compression is also useful in many applications other than remote computing and data transfer over a network. For example, image compression can effectively reduce the amount of memory required to save an image, whether at a thin client or at a network server.
Hence, what is needed is a method and an apparatus for compressing a digital image to reduce network bandwidth and memory use without requiring a significant amount of computational power.